package tree_1026;
public class TreeOperation {
    public static void preorder(TreeNode root) {
        if (root == null) {
            return;
        }

        System.out.println(root.val);
        preorder(root.left);
        preorder(root.right);
    }

    public static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        inorder(root.left);
        System.out.println(root.val);
        inorder(root.right);
    }

    public static void postorder(TreeNode root) {
        if (root == null) {
            return;
        }

        postorder(root.left);
        postorder(root.right);
        System.out.println(root.val);
    }

    // 统计二叉树第 k 层上结点个数
    // k >= 1
    public static int getKLevelNodeSize(TreeNode root, int k) {
        if (k < 1) {
            throw new RuntimeException("错误的 k 层数");
        }

        if (root == null) {
            // 当空树时，无论求第几层，结点个数都是 0 个
            return 0;
        }

        // root != null
        if (k == 1) {
            // 一棵非空树的第一层，只有一个根结点
            return 1;
        }

        // 剩余的情况就拆解成左子树和右子树的求解问题
        int leftSize = getKLevelNodeSize(root.left, k - 1);
        int rightSize = getKLevelNodeSize(root.right, k - 1);
        // 递归的过程中，树的规模在变小，k 的值也在变小
        // 意味着一定会走到 root == null 或者 k == 1 的情况
        return leftSize + rightSize;
    }

    public static TreeNode 手动构建二叉树() {
        TreeNode a = new TreeNode('A'); // 'A' 是 char 类型，char -> int 类型，就是这个字符的 unicode 编码（ascii 是 unicode 编码的子集）
        TreeNode b = new TreeNode('B');
        TreeNode c = new TreeNode('C');
        TreeNode d = new TreeNode('D');
        TreeNode e = new TreeNode('E');
        TreeNode f = new TreeNode('F');
        TreeNode g = new TreeNode('G');
        TreeNode h = new TreeNode('H');

        // 手动构建其关系
        a.left = b; a.right = c;
        b.left = d; b.right = e;
        c.left = f; c.right = g;
        d.left = null; d.right = null;  // 这行可以省略
        e.left = null; e.right = h;
        f.left = null; f.right = null;
        g.left = null; g.right = null;
        h.left = null; h.right = null;

        // 返回根结点即可
        return a;
    }

    public static void main1(String[] args) {
        TreeNode root = 手动构建二叉树();

        System.out.println(getKLevelNodeSize(root, 1));     //  1
        System.out.println(getKLevelNodeSize(root, 2));     //  2
        System.out.println(getKLevelNodeSize(root, 3));     //  4
        System.out.println(getKLevelNodeSize(root, 4));     //  1
        System.out.println(getKLevelNodeSize(root, 5));     //  0
        System.out.println(getKLevelNodeSize(root, 6));     //  0
    }

    public static int getHeightOf(TreeNode root) {
        if (root == null) {
            // 空树
            return 0;
        }

//        if (root.left == null && root.right == null) {
//            // 只有一个结点的树
//            return 1;
//        }

        int leftHeight = getHeightOf(root.left);
        int rightHeight = getHeightOf(root.right);

        return Integer.max(leftHeight, rightHeight) + 1;
    }

    public static void main2(String[] args) {
        TreeNode root = 手动构建二叉树();
        int h = getHeightOf(root);
        System.out.println(h);
    }

    public static boolean contains(TreeNode root, int target) {
        if (root == null) {
            return false;   // 空树中什么都不包含
        }

        // root != null
        // 按照前序遍历的方式进行查找：根 -> 左子树 -> 右子树
        // 注意：这个遍历可能不需要完整的走完

        // 先判断根的值是不是
        if (root.val == target) {
            // 根的值就是 target，所以二叉树中包含 target
            return true;    // 不需要继续去左右子树中再继续找了
        }

        // root != null && root.val != target
        // 先去左子树查找
        boolean r = contains(root.left, target);
        if (r == true) {
            // 说明左子树中找到了 target
            // 左子树中找到了target -> 整棵树中包含着 target
            // 所以
            return true;
        }

        // root != null && root.val != target && 左子树中没有找到
        // 再去右子树查找
        r = contains(root.right, target);
        if (r == true) {
            // 右子树中找到了 target
            // 右子树中找到了target -> 整棵树中包含着 target
            // 所以
            return true;
        } else {
            // 根我们比较过了 && 左子树我们找过了 && 右子树找过了
            // 都没有找到，所以
            return false;
        }
    }

    public static boolean containsNode(TreeNode root, TreeNode targetNode) {
        if (root == null) {
            return false;
        }

        // 根的比较
        // 同一性的比较：
        // root 和 targetNode 是不是同一个结点（逻辑）
        // root 引用 和 targetNode 引用是否指向的是同一个 TreeNode 对象
        // 使用 == 比较
        if (root == targetNode) {
            // root 和 targetNode 指向了同一个对象
            // 二叉树的根结点就是要找的结点
            // 所以
            return true;
        }

        boolean r = containsNode(root.left, targetNode);
        if (r == true) {
            return true;
        }

        r = containsNode(root.right, targetNode);
        if (r == true) {
            return true;
        } else {
            return false;
        }
    }

    // 找到包含 target 这个值所在的结点
    // target 在二叉树中时，返回包含 target 的 TreeNode 引用没有问题
    // target 不在二叉树中时，返回什么合适？   null 作为引用的特殊值，这个时候最合适
    // 当返回值 != null -> 找到了对应的结点，并且返回值就是这个结点
    // 当返回值 == null -> 没有找到对应的结点
    public static TreeNode nodeOf(TreeNode root, int target) {
        if (root == null) {
            // 空树，里面什么都没有，所以
            return null;    //  代表没有找到
        }

        // 根 -> 左子树 -> 右子树

        // 根
        if (root.val == target) {
            // 说明找到了，返回包含 target 的结点
            // 哪个引用指向了包含 target 值的结点对象？
            // root
            return root;
        }

        // 根里没有找到 target，接着去左子树中查找
        // 我们需要根据左子树的查找结果来判断是否找到，所以，需要保存左子树查找的结果
        TreeNode r = nodeOf(root.left, target);

        // 问，如何判断有没有在左子树中找到 target？
        // A. r.val == target     1) r 可能是 null，所以 r.val 可能空指针异常
        //                        2) 当 r != null 时，断言 r.val == target
        // B. r != null           【正确解答】
        if (r != null) {
            // 说明在左子树中找到了，返回一个包含 target 的结点
            // 问：现在哪个引用指向了包含 target 值的结点对象？
            // A: root              断言 root.val != target，否则轮不上左子树查找了
            // B: root.left         左子树中找到了，但不一定是左子树的根结点
            // C: r                 【正确解答】
            //                      r != null 时，断言 r.val == target
            return r;
        }

        // 根不是，左子树没找到，接着去右子树找
        r = nodeOf(root.right, target);

        if (r != null) {
            // 说明右子树中找到了，返回一个包含 target 的结点，就是右子树的查找结果
            return r;
        } else {
            // 说明根不是，左子树中没有找到，右子树中没有找到
            return null;        // 代表没有找到
        }
    }

    public static void main(String[] args) {
        TreeNode root = 手动构建二叉树();

        System.out.println(nodeOf(root, 'A'));
        System.out.println(nodeOf(root, 'B'));
        System.out.println(nodeOf(root, 'C'));
        System.out.println(nodeOf(root, 'D'));
        System.out.println(nodeOf(root, 'E'));
        System.out.println(nodeOf(root, 'F'));
        System.out.println(nodeOf(root, 'G'));
        System.out.println(nodeOf(root, 'H'));  // (H)
        System.out.println(nodeOf(root, 'I'));  // null
    }
}
